import java.util.Scanner;

class AVLTreeNode {
    public int val;
    AVLTreeNode parent;//孩子双亲表示法
    AVLTreeNode left;
    AVLTreeNode right;
    int bf;//平衡因子
    public AVLTreeNode(int val) {
        this.val = val;
    }
}
public class E2T2 {
    //AVL树是高度平衡的二叉搜索树,AVL树插入结点前仍然是AVL树
    //1.二叉搜索树的插入
    public static AVLTreeNode BSTInsert(AVLTreeNode cur,AVLTreeNode root) {
        AVLTreeNode tmp = root;
        AVLTreeNode parent = null;
        while(tmp!=null) {
            if(tmp.val>cur.val) {
                parent = tmp;
                tmp = tmp.left;
            }else if(tmp.val< cur.val) {
                parent = tmp;
                tmp = tmp.right;
            }else {
                return root;
            }
        }
        if(cur.val< parent.val) {
            parent.left = cur;
        }else {
            parent.right = cur;
        }
        return root;
    }
    public static AVLTreeNode AVLInsert(AVLTreeNode cur,AVLTreeNode root) {
        AVLTreeNode parent = BSTInsert(cur,root);
        while(parent!=null) {
            //调整parent结点平衡因子
            if(cur==parent.left) {
                parent.bf--;
            }else if(cur==parent.right){
                parent.bf++;
            }
            if(parent.bf==0)  {
                break;//说明原来parent.bf是+-1,没有增加树的深度,不会影响平衡性
            }else if(parent.bf==1||parent.bf==-1) {
                cur = parent;
                parent = cur.parent;//说明原来parent.bf是0,现在树的深度增加了1,需要继续向上调整
            }else {
                //说明原来parent.bf是+-1,现在已经不平衡了,需要进行旋转.
                if(parent.bf==2) {
                    //左树深,需要进行右旋
                    AVLTreeNode pSubR = parent.right;
                    if(pSubR.bf==1) {
                        //进行右单旋
                        rotateRight(parent,root);
                    }else if(pSubR.bf==-1){
                        //进行左右旋
                        rotateLR(parent,root);
                    }
                }else {
                    AVLTreeNode pSubL = parent.left;
                    //右树深,需要进行左旋
                    if(pSubL.bf==1) {
                        //进行左单旋
                        rotateLeft(parent,root);
                    }else if(pSubL.bf==-1) {
                        //进行右左旋
                        rotateRL(parent,root);
                    }
                }
            }
        }
        return root;
    }
    private static void rotateLeft(AVLTreeNode parent,AVLTreeNode root) {
        AVLTreeNode subR = parent.right;
        AVLTreeNode subRL = subR.left;
        parent.right = subRL;
        if(subRL!=null) {
            subRL.parent = parent;
        }
        AVLTreeNode pParent = parent.parent;
        subR.left = parent;
        parent.parent = subR;
        if(parent==root) {
            root = subR;
            root.parent = null;
        }else if(parent == pParent.left){
            pParent.left = subR;
            subR.parent = pParent;
        }else if(parent==pParent.right) {
            pParent.right = subR;
            subR.parent = pParent;
            subR.bf = 0;
            parent.bf = 0;
        }
    }
    private static void rotateRight(AVLTreeNode parent,AVLTreeNode root) {
        AVLTreeNode subL = parent.left;
        AVLTreeNode subLR = subL.right;
        if(subLR!=null) {
            subLR.parent = parent;
        }
        AVLTreeNode pParent = parent.parent;
        subL.right = parent;
        parent.parent = subL;
        if(parent==root) {
            root = subL;
            root.parent = null;
        }else if(parent == pParent.left){
            pParent.left = subL;
            subL.parent = pParent;
        }else if(parent==pParent.right) {
            pParent.right = subL;
            subL.parent = pParent;
            subL.bf = 0;
            parent.bf = 0;
        }
    }

    private static void rotateLR(AVLTreeNode parent,AVLTreeNode root) {
        AVLTreeNode subL = parent.left;
        AVLTreeNode subLR = subL.right;
        int bf = subLR.bf;
        rotateLeft(subL,root);
        rotateRight(parent,root);
        if(bf==1) {
            subL.bf = 0;
            parent.bf = 1;
        }else if(bf==-1) {
            subL.bf = -1;
            parent.bf = 0;
        }
        subLR.bf = 0;
    }
    private static void rotateRL(AVLTreeNode parent,AVLTreeNode root) {
        AVLTreeNode subR = parent.right;
        AVLTreeNode subRL = subR.right;
        int bf = subRL.bf;
        rotateRight(subR,root);
        rotateLeft(parent,root);
        if(bf==1) {
            subR.bf = -1;
            parent.bf = 0;
        }else if(bf==-1) {
            subR.bf = 0;
            parent.bf = 1;
        }
        subRL.bf = 0;
    }
    public static void preOrder(AVLTreeNode root,StringBuilder stringBuilder) {
        if(root==null) {
            stringBuilder.append("#");
            return;
        }
        preOrder(root.left,stringBuilder);
        stringBuilder.append(root.val+"");
        preOrder(root.right,stringBuilder);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String[] order = scanner.nextLine().split(" ");
        AVLTreeNode root = null;
        for (int i = 0; i < n; i++) {
            if(i==0) {
                root = new AVLTreeNode(Integer.valueOf(order[i]));
                continue;
            }
            root = AVLInsert(new AVLTreeNode(Integer.valueOf(order[i])),root);
        }
        StringBuilder stringBuilder = new StringBuilder();
        preOrder(root,stringBuilder);
        System.out.println(stringBuilder);
    }
}
